package com.zto.sch.advance.algorithms.nowcoder.offer;

import org.junit.Test;

import java.util.Arrays;
import java.util.Objects;

/**
 * @program: sch-diy-parent
 * @description:
 * 题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
 * 对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
 * 例：
 * 输入：[1,2,3,4,5]
 * 返回值：[120,60,40,30,24]
 *
 * @author: sch
 * @create: 2021-07-04 23:03
 **/
public class 构建乘积数组 {
    @Test
    public void test() {
        int[] originArr = {1, 2, 3, 4, 5};
        System.out.println("origin:" + Arrays.toString(originArr));

        int[] afterArr = multiplyArr(originArr);

        System.out.println("after multiply:" + Arrays.toString(afterArr));

    }

    /**
     * 通过 B|i|=A|0|×A|1|×…×A|i-1|×A|i+1|×…×A|n-1|
     * 我们发现 B|i| 就是 A|i| 左边所有元素的积 乘 A|i| 右边所有元素的积。
     * <p>
     * 对称遍历
     * 从左往右遍历累乘，结果保存在数组 retret 中，此时 ret|i| 表示，A|i| 左边所有元素的乘积
     * 然后从右往左遍历累乘，获取A|i| 右边所有元素的乘积
     * 两边遍历之后得到的 retret，就是最终结果
     *
     * @param A
     * @return
     */
    private int[] multiplyArr(int[] A) {
        if (Objects.isNull(A) || A.length < 1) {
            System.out.println("参数有误");
        }

        int[] B = new int[A.length];
        int left = 1;
        for (int i = 0; i < A.length; i++) {
            B[i] = left;
            left = left * A[i];
        }

        int right = 1;
        for (int i = A.length - 1; i >= 0; i--) {
            B[i] *= right;
            right *= A[i];
        }

        return B;
    }

    public static void main(String[] args) {
        int[] aa = {1, 2, 3, 4, 5};
        int length = aa.length;
        int[] bb = new int[length];


        int left = 1;
        for (int i = 0; i < length; i++) {
            bb[i] = left;
            left *= aa[i];
        }

        int right = 1;
        for (int i = length - 1; i >= 0; i--) {
            bb[i] *= right;
            right *= aa[i];
        }

        System.out.println(Arrays.toString(aa));
        System.out.println(Arrays.toString(bb));
    }

}
